package algorithm;

public class MergeSort {
    private  int[] temp;
    public int[] merge_sort(int[] nums) {
        this.temp = new int[nums.length];
        mergeSort(nums, 0, nums.length - 1);
        return nums;
    }

    public void mergeSort(int[] nums, int left, int right) {
        if(left == right) return;
        int mid = left + (right - left) / 2;
        mergeSort(nums, left, mid);
        mergeSort(nums, mid + 1, right);
        merge(nums, left, right, mid);
    }

    public void merge(int[] nums, int left, int right, int mid) {
        int l = left, r = mid + 1;
        int ptr = left;
        while(l <= mid && r <= right) {
            temp[ptr++] = nums[l] <= nums[r] ? nums[l++] : nums[r++];
        }

        while(l <= mid) {
            temp[ptr++] = nums[l++];
        }

        while(r <= right) {
            temp[ptr++] = nums[r++];
        }

        if (right + 1 - left >= 0)
            System.arraycopy(temp, left, nums, left, right + 1 - left);
    }
}
